import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Node implements Comparable<Node> {
    char ch;
    int freq;
    Node left;
    Node right;

    public Node(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
    }

    // 定义比较运算符，用于优先队列的排序
    @Override
    public int compareTo(Node other) {
        return this.freq - other.freq;
    }
}

public class HuffmanCoding {

    // 构建哈夫曼树
    public static Node buildHuffmanTree(String text) {
        // 统计字符频率
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char ch : text.toCharArray()) {
            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
        }

        // 构建优先队列（最小堆）
        PriorityQueue<Node> heap = new PriorityQueue<>();
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            heap.add(new Node(entry.getKey(), entry.getValue()));
        }

        // 合并节点构建哈夫曼树
        while (heap.size() > 1) {
            Node node1 = heap.poll();
            Node node2 = heap.poll();

            // 创建新节点，其频率为两个子节点频率之和
            Node merged = new Node('\0', node1.freq + node2.freq);
            merged.left = node1;
            merged.right = node2;

            // 将新节点加入到优先队列中
            heap.add(merged);
        }

        // 返回哈夫曼树的根节点
        return heap.poll();
    }

    // 生成哈夫曼编码
    public static void generateHuffmanCodes(Node root, String code, Map<Character, String> huffmanCodes) {
        if (root == null) return;

        // 如果是叶子节点，保存编码
        if (root.left == null && root.right == null) {
            huffmanCodes.put(root.ch, code);
        }

        // 递归遍历左子树和右子树
        generateHuffmanCodes(root.left, code + "0", huffmanCodes);
        generateHuffmanCodes(root.right, code + "1", huffmanCodes);
    }

    // 哈夫曼编码主函数
    public static Map<Character, String> huffmanEncoding(String text) {
        // 构建哈夫曼树
        Node root = buildHuffmanTree(text);

        // 生成哈夫曼编码
        Map<Character, String> huffmanCodes = new HashMap<>();
        generateHuffmanCodes(root, "", huffmanCodes);

        return huffmanCodes;
    }

    // 使用哈夫曼编码对文本进行编码
    public static String encodeText(String text, Map<Character, String> huffmanCodes) {
        StringBuilder encodedText = new StringBuilder();
        for (char ch : text.toCharArray()) {
            encodedText.append(huffmanCodes.get(ch));
        }
        return encodedText.toString();
    }

    // 测试程序
    public static void main(String[] args) {
        String text = "aabc";

        // 获取哈夫曼编码
        Map<Character, String> huffmanCodes = huffmanEncoding(text);
        
        System.out.println("哈夫曼编码: " + huffmanCodes);

        // 对文本进行编码
        String encodedText = encodeText(text, huffmanCodes);
        System.out.println("编码后的文本: " + encodedText);
    }
}
